// Copyright (c) 2020-present, INSPUR Co, Ltd. All rights reserved.
// This source code is licensed under Apache 2.0 License.
//
// Created by florian on 05.08.15.

#pragma once
#include <atomic>
#include <stdint.h>
#include <string.h>
#include "abstract_loadkey.h"
#include "art_key.h"
#include "pure_mem/epoche.h"

namespace art_rowex {

enum class NTypes : uint8_t { N4 = 0, N16 = 1, N48 = 2, N256 = 3 };

static constexpr uint32_t maxStoredPrefixLength = 4;
struct Prefix {
  uint32_t prefixCount = 0;
  uint8_t prefix[maxStoredPrefixLength];
};
static_assert(sizeof(Prefix) == 8, "Prefix should be 64 bit long");

// N class is abstract class for all node in ART tree.
// and support general function like insert \ nodeType \ lock etc.
class N {
 protected:
  N(NTypes type, uint32_t level1, const uint8_t *prefix1,
    uint32_t prefixLength1)
      : level(level1) {
    setType(type);
    setPrefix(prefix1, prefixLength1);
  }

  N(NTypes type, uint32_t level1, const Prefix &prefi)
      : prefix_(prefi), level(level1) {
    setType(type);
  }

  N(const N &) = delete;

  N(N &&) = delete;

  void setType(NTypes type);

  static uint64_t convertTypeToVersion(NTypes type);

  // 2b type 60b version 1b lock 1b obsolete
  std::atomic<uint64_t> typeVersionLockObsolete{0b100};
  // version 1, unlocked, not obsolete
  std::atomic<Prefix> prefix_;
  const uint32_t level;
  uint16_t count = 0;
  uint16_t compactCount = 0;

 public:
  NTypes getType() const;

  uint32_t getLevel() const;

  uint32_t getCount() const;

  void writeLockOrRestart(bool &needRestart);

  void lockVersionOrRestart(uint64_t &version, bool &needRestart);

  void writeUnlock();

  uint64_t getVersion() const;

  // returns true if node hasn't been changed in between
  bool checkOrRestart(uint64_t startRead) const;
  bool readUnlockOrRestart(uint64_t startRead) const;

  static bool isObsolete(uint64_t version);

  // can only be called when node is locked
  void writeUnlockObsolete() { typeVersionLockObsolete.fetch_add(0b11); }

  static bool isLocked(uint64_t version);

  static N *getChild(const uint8_t k, N *node);

  static void insertAndUnlock(N *node, N *parentNode, uint8_t keyParent,
                              uint8_t key, N *val, bool &needRestart);

  static void change(N *node, uint8_t key, N *val);

  static void removeAndUnlock(N *node, uint8_t key, N *parentNode,
                              uint8_t keyParent, bool &needRestart);

  Prefix getPrefi() const;

  void setPrefix(const uint8_t *prefix, uint32_t length);

  void addPrefixBefore(N *node, uint8_t key);

  static TID getLeaf(const N *n);

  static bool isLeaf(const N *n);

  static N *setLeaf(TID tid);

  static N *getAnyChild(const N *node);

  static TID getAnyChildTid(const N *n);

  static void deleteChildren(N *node);

  static void deleteNode(N *node);

  static std::tuple<N *, uint8_t> getSecondChild(N *node, const uint8_t key);

  template <typename curN, typename biggerN>
  static void insertGrow(curN *n, N *parentNode, uint8_t keyParent, uint8_t key,
                         N *val, bool &needRestart);

  template <typename curN>
  static void insertCompact(curN *n, N *parentNode, uint8_t keyParent,
                            uint8_t key, N *val, bool &needRestart);

  template <typename curN, typename smallerN>
  static void removeAndShrink(curN *n, N *parentNode, uint8_t keyParent,
                              uint8_t key, bool &needRestart);

  static void getChildren(const N *node, uint8_t start, uint8_t end,
                          std::tuple<uint8_t, N *> children1[],
                          uint32_t &childrenCount);

};

// N4 class is node type in ART tree, store four children at most.
class N4 : public N {
 public:
  std::atomic<uint8_t> keys[4];
  std::atomic<N *> children[4];

 public:
  N4(uint32_t level1, const uint8_t *prefix1, uint32_t prefixLength1)
      : N(NTypes::N4, level1, prefix1, prefixLength1) {
    memset(keys, 0, sizeof(keys));
    memset(children, 0, sizeof(children));
  }

  N4(uint32_t level1, const Prefix &prefi) : N(NTypes::N4, level1, prefi) {
    memset(keys, 0, sizeof(keys));
    memset(children, 0, sizeof(children));
  }

  bool insert(uint8_t key, N *n);

  template <class NODE>
  void copyTo(NODE *n) const;

  void change(uint8_t key, N *val);

  N *getChild(const uint8_t k) const;

  bool remove(uint8_t k, bool force);

  N *getAnyChild() const;

  std::tuple<N *, uint8_t> getSecondChild(const uint8_t key) const;

  void deleteChildren();

  void getChildren(uint8_t start, uint8_t end,
                   std::tuple<uint8_t, N *> *&children1,
                   uint32_t &childrenCount) const;
};

// N16 class is node type in ART tree, store sixteen children at most.
class N16 : public N {
 public:
  std::atomic<uint8_t> keys[16];
  std::atomic<N *> children[16];

  static uint8_t flipSign(uint8_t keyByte) {
    // Flip the sign bit, enables signed SSE comparison of unsigned values, used
    // by Node16
    return keyByte ^ 128;
  }

  static inline unsigned ctz(uint16_t x) {
    // Count trailing zeros, only defined for x>0
#ifdef __GNUC__
    return __builtin_ctz(x);
#else
    // Adapted from Hacker's Delight
    unsigned n = 1;
    if ((x & 0xFF) == 0) {
      n += 8;
      x = x >> 8;
    }
    if ((x & 0x0F) == 0) {
      n += 4;
      x = x >> 4;
    }
    if ((x & 0x03) == 0) {
      n += 2;
      x = x >> 2;
    }
    return n - (x & 1);
#endif
  }

  std::atomic<N *> *getChildPos(const uint8_t k);

 public:
  N16(uint32_t level1, const uint8_t *prefix1, uint32_t prefixLength1)
      : N(NTypes::N16, level1, prefix1, prefixLength1) {
    memset(keys, 0, sizeof(keys));
    memset(children, 0, sizeof(children));
  }

  N16(uint32_t level1, const Prefix &prefi) : N(NTypes::N16, level1, prefi) {
    memset(keys, 0, sizeof(keys));
    memset(children, 0, sizeof(children));
  }

  bool insert(uint8_t key, N *n);

  template <class NODE>
  void copyTo(NODE *n) const;

  void change(uint8_t key, N *val);

  N *getChild(const uint8_t k) const;

  bool remove(uint8_t k, bool force);

  N *getAnyChild() const;

  void deleteChildren();

  void getChildren(uint8_t start, uint8_t end,
                   std::tuple<uint8_t, N *> *&children1,
                   uint32_t &childrenCount) const;
};

// N48 class is node type in ART tree, store 48 children at most.
class N48 : public N {
  std::atomic<uint8_t> childIndex[256];
  std::atomic<N *> children[48];

 public:
  static const uint8_t emptyMarker = 48;

  N48(uint32_t level1, const uint8_t *prefix1, uint32_t prefixLength1)
      : N(NTypes::N48, level1, prefix1, prefixLength1) {
    memset(childIndex, emptyMarker, sizeof(childIndex));
    memset(children, 0, sizeof(children));
  }

  N48(uint32_t level1, const Prefix &prefi) : N(NTypes::N48, level1, prefi) {
    memset(childIndex, emptyMarker, sizeof(childIndex));
    memset(children, 0, sizeof(children));
  }

  bool insert(uint8_t key, N *n);

  template <class NODE>
  void copyTo(NODE *n) const;

  void change(uint8_t key, N *val);

  N *getChild(const uint8_t k) const;

  bool remove(uint8_t k, bool force);

  N *getAnyChild() const;

  void deleteChildren();

  void getChildren(uint8_t start, uint8_t end,
                   std::tuple<uint8_t, N *> *&children48,
                   uint32_t &childrenCount) const;
};

// N256 class is node type in ART tree, can store 256 children.
class N256 : public N {
  std::atomic<N *> children[256];

 public:
  N256(uint32_t level1, const uint8_t *prefix1, uint32_t prefixLength1)
      : N(NTypes::N256, level1, prefix1, prefixLength1) {
    memset(children, '\0', sizeof(children));
  }

  N256(uint32_t level1, const Prefix &prefi) : N(NTypes::N256, level1, prefi) {
    memset(children, '\0', sizeof(children));
  }

  bool insert(uint8_t key, N *val);

  template <class NODE>
  void copyTo(NODE *n) const;

  void change(uint8_t key, N *n);

  N *getChild(const uint8_t k) const;

  bool remove(uint8_t k, bool force);

  N *getAnyChild() const;

  void deleteChildren();

  void getChildren(uint8_t start, uint8_t end,
                   std::tuple<uint8_t, N *> *&children256,
                   uint32_t &childrenCount) const;
};

template <class NODE>
void N4::copyTo(NODE *n) const {
  for (uint32_t i = 0; i < compactCount; ++i) {
    N *child = children[i].load();
    if (child != nullptr) {
      n->insert(keys[i].load(), child);
    }
  }
}

template <class NODE>
void N16::copyTo(NODE *n) const {
  for (unsigned i = 0; i < compactCount; i++) {
    N *child = children[i].load();
    if (child != nullptr) {
      n->insert(flipSign(keys[i]), child);
    }
  }
}

template <class NODE>
void N48::copyTo(NODE *n) const {
  for (unsigned i = 0; i < 256; i++) {
    uint8_t index = childIndex[i].load();
    if (index != emptyMarker) {
      n->insert(i, children[index]);
    }
  }
}

template <class NODE>
void N256::copyTo(NODE *n) const {
  for (int i = 0; i < 256; ++i) {
    N *child = children[i].load();
    if (child != nullptr) {
      n->insert(i, child);
    }
  }
}
}  // namespace art_rowex
